package com.zbl.小题大做;

/*
第一步确定结果范围，最难。一般考虑极端条件，超出最优结果范围也可以，不用精确
第二步结果范围和条件限制建立单调性
第三步上二分
 */
public class 二分 {


    // 在有序数组arr上，找到大于等于value的最左值
    public static int nearest(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;

        int ans = -1;
        while (L <= R) {
            int mid = (R + L) / 2;// (R + L) >> 1; (R-L) >> 1 + L;
            if (arr[mid] >= value) {
                ans = arr[mid];
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        return ans;
    }

    // 有arr堆香蕉，一小时只能吃完一堆或达到最大数，timeLimit是总时间限制
    // 问，每小时最少吃多少个香蕉，能保证全部吃完
    public static int eatBanner(int[] arr, int timeLimit) {
        if (arr.length > timeLimit) {
            throw new RuntimeException("太多了，吃不完");
        }

        int L = 1;
        int R = 0;
        for (int i : arr) {
            R = Math.max(R, i);
        }

        int ans = 0;
        int speed = 0;
        while (L <= R) {
            speed = (L + R) / 2;
            if (eatTime(arr, speed) <= timeLimit) {
                ans = speed;
                R = speed - 1;
            } else {
                L = speed + 1;
            }
        }

        return ans;
    }
    public static int eatTime(int[] arr, int speed) {
        int eatTime = 0;
        int offset =  speed - 1;

        for (int i : arr) {
            eatTime += (offset + i) / speed;
        }

        return eatTime;
    }

    // arr存的是每个工作需要的时间，worker是工人数量，工人只能接连续的工作任务
    //  问，最少需要多少时间，能完成所有任务
    // 思路：1、工作最大时间等于所有工作时间之和，最小时间是最大的那个工作的时间；2、保证在划定的工作时间范围内，完成任务；3、上二分
    public static int workTime(int[] arr, int worker) {
        int L = 0;
        int R = 0;
        for (int i : arr) {
            R += i;
            L = Math.max(L, i);
        }

        int ans = -1;
        int workerTime = 0;
        while (L <= R) {
            workerTime = (L + R) >> 1;
            if (doWork(arr, workerTime, worker)) {
                ans = workerTime;
                R = workerTime - 1;
            } else {
                L = workerTime + 1;
            }
        }

        return ans;
    }
    // 返回实际最小工作时间
    public static boolean doWork(int[] arr, int maxTime, int worker) {
        int workerTime = 0;
        for (int i : arr) {
            if (workerTime + i > maxTime) {
                worker -= 1;
                if (worker == 0) {
                    return false;
                }
                workerTime = i;
            } else {
                workerTime += i;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println(workTime(new int[]{1, 2, 4, 5, 6, 7, 8, 9, 10}, 2));
    }
}
